前言

今天帶兩題題目，一題跟 stack 相關一題跟 queue 相關，為的是讓大家可以更了解怎麼應用這些資料結構，而不是只有瞭解概念

UVa 10935 Throwing cards away I

題目說明

題目會給定一個數字 代表有編號 ~ 的紙牌，題目要求要把第一張排輸出並丟掉，接下來要把最上面的牌再放到最底下

解題思路

仔細思考題目就會發現它是每一次都輸出最上面的牌，接下來丟掉，然後再把最上面的牌放到最下方，所以基本上它會是一個 queue 的操作，每次動作就是先輸出最頂端再把資料丟掉，接下來再把最頂端的資料放到最下方，重複這樣的動作直到 queue 內部沒資料為止

時間複雜度

AC Code

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n;  
    while(cin >> n && n){
        queue <long long> card;
        for(int i = 1;i <= n;i++){
            card.push(i);
        }
        cout << "Discarded cards:";
        int f = 0;
        while(card.size() != 1){
            int x = card.front();
            card.pop();
            if(card.size() && f){
                cout << ",";
            }
            cout << " " << x;
            card.push(card.front());
            card.pop();
            f = 1;
        }
        cout << "\nRemaining card: " << card.front() << "\n";
    }
    return 0;
}

a565. 2.p&q的邂逅

題目說明

每筆測資第一行會給 ，代表有 行字串，每筆字串會由 、、 三個字元組成，而最終要算出可以配對成 、 的數量並輸出

解題思路

仔細想一下會發現如果你一遇到 就把它放進 stack 中，接下來如果遇到 就看看 stack 中有沒有可以配對的，如果有就先把答案加 再把 stack 中的元素 pop 掉，沒有就都不管，這樣最後得到的就會是數量

時間複雜度

AC Code

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); 
    long long n;
    cin >> n;
    string s;
    while(n--){
        long long ans = 0;
        stack<char> stk;
        cin >> s;
        for(int i = 0;i < s.size();i++){
            if(!stk.empty() && stk.top() == 'p' && s[i] == 'q'){
                ans++;
                stk.pop();
            }else if(s[i] == 'p'){
                stk.push(s[i]);
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

總結

可以看到其實有些題目是可以很直觀的用堆疊跟佇列解，不過在競賽的時候大多都是搭配著演算法去做使用，例如之後會提到的 BFS，就有用到 queue 的概念，因此，多多瞭解資料結構的運作原理也可以讓你在學習演算法的過程中更加輕鬆且容易理解

預告

明天就是基礎資料結構的最後一天了，後面就比較多內容會是演算法，題目應該也會多上不少，大家可以好好期待一下